package assign1;
/* COMP 3760 - Algorithm Analysis and Design
 * Assignment #1 - Mnemonic Monkey
 * Stacy Mitchell	A00816991
 * Vukasin Simic	A00801474
 * 
 * October 14, 2012
 * 
 * Mnemonic.java
 * 
 * To run:
 * cd ...\src
 * javac assign1\*.java
 * java assign1.Mnemonic < sample_input.txt > output.txt
 * 
 * Driver class that runs the program simulating Keanu the Orangutan's traversal of paths between Pharmaceutical Research Labs in a tropical rainforest.
 * 
 * Utilizes the Subset class to record individual combinations of labs that can be visited in a single trip, the amount of MemoryRequired for the trip,
 * and the fastest possible ordering of labs to visit.
 * 
 * Utilizes the abstract Permutation class, for its LexicographicPermute algorithm, used to generate all possible permutations of each candidate Subset.
 * Utilizes the abstract Subsets class, to generate all subsets of the Test case's labs.
 * 
 * 
 * Reads the first line to determine the number of Test Cases to be provided.
 * For each Test Case reads and records the required input, then proceeds to determining the optimal paths Keanu can take
 * to generate the most revenue in the least amount of time, and as early as possible in the week.
 * 
 */
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

public class Mnemonic {
	static final int CHIP_MEMORY_AVAILABLE = 56;
	static final double MONKEY_SPEED_KMH = 1;
	static final int METRES_IN_A_KILOMETRE = 1000;
	static final int WORK_HOURS = 12;
	static final int PRICE_PER_MB = 1000;
	static final double MAX_TIME = 120; //Max program runtime in seconds before forced exit
	
	public static void main(String[] args) {
		Scanner input_scan = new Scanner(System.in);
		int num_test_cases;
		int num_labs;
		List<Map<String, Integer>> lab_list;
		boolean[] no_mem_labs; //record of which labs have no data
		List<Subset> all_valid_subsets; // All subsets of 'labs to visit in a trip' that do not include any 0 memory labs and are below the Memory limit
		Subset optimal_set; // the set containing the fastest and best permutation, path Keanu can take
		List<Integer> visited_labs; //record of which labs Keanu has visited
		int weekday; //current day of the week (1=Monday, 2= Tuesday, ...)
		int optimal_set_index; //location of the optimal set in the all_valid_subsets list
		List<Integer> best_permutation; // the best arrangement of the optimal set
		double best_time; // the time needed by Keanu to complete the optimal path
		double total_time; //the time Keanu takes to complete all the paths in a week
		long caseStartTime; //time when execution of a case began
		long programStartTime = System.nanoTime(); //time when execution of the entire program began
		
		//Get number of test cases
		num_test_cases = input_scan.nextInt();
		input_scan.nextLine();
		
		//Loop through all provided cases
		for (int i = 1; i <= num_test_cases; i++){			
			lab_list = new ArrayList<Map<String, Integer>>();
			
			//Get number of labs in each test case
			num_labs = input_scan.nextInt();
			input_scan.nextLine();
			
			Map<String, Integer> lab_info;
			//Get each lab's coordinates
			for (int j = 0; j < num_labs; j++){
				lab_info = new HashMap<String, Integer>(); 
				lab_info.put("x-coordinate", input_scan.nextInt());
				lab_info.put("y-coordinate", input_scan.nextInt());
				lab_list.add(lab_info);
				input_scan.nextLine();
			}
	
			//Get each lab's required-data amount
			int memory_required;
			no_mem_labs = new boolean[num_labs];
			for (int k = 0; k < num_labs; k++){
				memory_required = input_scan.nextInt();
				if(memory_required == 0){
					no_mem_labs[k] = true;
				}
				lab_list.get(k).put("memory_required", memory_required);
			}
			
			input_scan.nextLine();
			//=================End of Input scanning===================
			
			System.out.println("Test " + i);
			caseStartTime = System.nanoTime();
			
			//Get all possible subsets of the labs that can be visited, minus those sets that exceed the memory limit or have labs with no data
			all_valid_subsets = Subsets.getSubsets(num_labs - 1, no_mem_labs, lab_list, CHIP_MEMORY_AVAILABLE, programStartTime, caseStartTime); //
			
			//Sort all the subsets in descending order of how much total data they contain
			Collections.sort(all_valid_subsets, Subset.MemoryComparator);
			
			//Begin execution of the test case week
			total_time = 0;
			visited_labs = new ArrayList<Integer>();
			weekday = 1;
			boolean allLabsVisited = false;
			
			//Keanu will keep attempting to make trips until the week is over, OR he has visited all the labs, OR*
			while ((weekday < 6) && !allLabsVisited){
				//use the getOptimalPath algorithm on the sorted list of subsets to determine the set with the fastest/best permutation
				optimal_set_index = getOptimalPath(all_valid_subsets, lab_list, visited_labs, programStartTime, caseStartTime);
				
				//*If the getOptimalPath returns -1: no optimal path exists. Likely, the remaining labs are unreachable given the time limit.
				if(optimal_set_index == -1){
					weekday = 7; //Since remaining labs are unreachable, end the week prematurely
				}else{
					//retrieve the optimal set's details(best permutation and best time)
					optimal_set = all_valid_subsets.get(optimal_set_index);
					best_time = optimal_set.getBest_time();
					total_time += best_time;
					best_permutation = optimal_set.getBest_permutation();
					
					//Display result of taking the optimal path
					displayDailyResult(weekday, best_permutation, best_time);
					
					//Update the record of which labs have been visited so far
					for (int lab_num : best_permutation){
						if (!visited_labs.contains(lab_num) && lab_num != 0){// do not add home lab to the visited labs list, as the home lab may be visited multiple times.
							visited_labs.add(lab_num);
						}
					}
					allLabsVisited = visited_labs.size() == num_labs -1; //Update allLabsVisited boolean check
					
					weekday++; //move to next day
				}
			}//End of, loop through weekdays
			
			//End of week, display total results of all weekly trips
			displayEndWeekResult(visited_labs, num_labs, lab_list, total_time, caseStartTime);

		}//End of, loop going through all given cases
	}//End of Main
	
	
	//Display end of day result, which path was taken
	public static void displayDailyResult(int weekday, List<Integer> best_permutation, double best_time){
		String labs_visited = "";
		for (int i = 0; i < best_permutation.size(); i++){
			labs_visited += " " + (best_permutation.get(i) + 1);
		}
		
		System.out.printf("  Day %d:%s [%.2f km]\n", weekday, labs_visited, best_time * MONKEY_SPEED_KMH);
	}
	
	//Display end of week result, summary of all trips taken during the week.
	public static void displayEndWeekResult(List<Integer> visited_labs, int num_labs, List<Map<String, Integer>> lab_list, double total_time, long caseStartTime){
		String labs_not_visited = "";
		int data_remaining = 0;
		long caseEndTime = System.nanoTime();
		double runTimeInMs = (caseEndTime - caseStartTime)/Math.pow(10, 6);
		
		if(visited_labs.size() != num_labs -1){
			for(int k = 1; k < num_labs; k++){
				if(!visited_labs.contains(k)){
					labs_not_visited += (k + 1) + " ";
					data_remaining += lab_list.get(k).get("memory_required");
				}
			}
			System.out.printf("\n  Missed files from labs: %s[$%d]\n", labs_not_visited, data_remaining * PRICE_PER_MB);
		}
		System.out.printf("\n  Total work time: %.1f h\n", total_time);
		System.out.printf("\n  execution time %.3f ms\n\n", runTimeInMs);
	}
	
	/* Algorithm used to find the optimal path to take.
	 * Accepts list of Subset objects(possible lab combinations) to visit in one trip, lab details(coordinates, memory, already visited), 
	 * and program/case start time(to timeout in case of excessive runtime).
	 * Returns the index of the optimal Subset object in the list of Subset objects, which has been updated to include its optimal permutation and corresponding runtime.
	 * 
	 * Iterates through the list of Subset objects sorted in descending order of MemoryRequired.
	 * 
	 * Look at the Subset with the largest amount of memory required (first in the list) and any other subsequent Subset objects
	 * with the same amount of memory. Select the one with fastest arrangement of labs, if the time is less than WORK_HOURS
	 * that Subset.
	 * 
	 * But if the time of the Subset is greater than WORK_HOURS, descend through the list checking the Subsets with incrementally
	 * less MemoryRequired, until the fastest Subset with time less than WORK_HOURS is found.
	 * 
	 * If no valid optimal Subset is found, returns -1, indicating that no optimal path exists as the labs cannot be reached
	 * in the limited time provided.
	 * 
	 * Any Subset objects containing lab numbers already visited (specified in the visited_labs List), are omitted from inspection.
	 * 
	 * Note to Developers: Sorted list of Subset objects 'might' serve its purpose better as a HashMap with keys equal to MemoryRequired and,
	 * values equal to a list of all Subset objects that with the corresponding amount of MemoryRequired.
	 */
	public static int getOptimalPath(List<Subset> all_valid_subsets, List<Map<String, Integer>> lab_list, 
			List<Integer> visited_labs, long programStartTime, long caseStartTime){
		
		int num_sets = all_valid_subsets.size();
		int largest_memory = all_valid_subsets.get(0).getMemory_required(); //Current largest memory so far in the set
		int current_set_memory;
		List<Integer> best_set_permutation = null; // The fastest arrangement of a Subset
		double best_set_time = Integer.MAX_VALUE; // The time of the Subset's fastest arrangement
		double best_overall_time = Integer.MAX_VALUE; // The smallest permutation time observed so far
		//index of the Subset object within the Subset list, with the largest MemoryRequired, and the fastest valid(within the WORK_HOURS time limit) time
		int best_overall_set_index = -1; 
		Subset current_set; // The Subset object being inspected for its fastest permutation and time
		
		int j = 0;
		//Iterate through all_valid_subsets 
		while (j < num_sets){
			/* When done checking sets with largest Memory value, return the set with the fastest permutation, 
			 * UNLESS the time required is less than is available.
			 */
			if ((current_set_memory = (current_set = all_valid_subsets.get(j)).getMemory_required()) != largest_memory){
				
				if (best_overall_time <= WORK_HOURS){
					return best_overall_set_index;
				}else{
					largest_memory = current_set_memory;
					best_overall_time = Integer.MAX_VALUE;
				}
			}
			
			//If current Subset does NOT contain any labs already visited, inspect it
			if (!listContainsAnyOf(current_set.getList(), visited_labs)){
				/*Update each Subset object to include its fastest permutation, UNLESS object was already updated on a previous run in the week,
				  in which case, get the current set's permutation Best_time for comparison with other Subset objects.*/
				if (current_set.getBest_permutation() != null){
					best_set_time = current_set.getBest_time();
				}else{
					checkTimeout(programStartTime, caseStartTime); //check that Program Runtime has not exceeded time limit
					//Generate, all the set's permutations, check for the optimal one
					best_set_permutation = Permutation.lexicographicPermute(current_set.getList(), lab_list, programStartTime, caseStartTime);
					best_set_time = getPathTimeInHours(lab_list, best_set_permutation);
					
					//Record the fastest permutation that exists in the Subset. Update the Subset object.
					current_set.setBest_time(best_set_time);
					current_set.setBest_permutation(best_set_permutation);
				}
				
				//Record the Subset containing the fastest permutation seen so far
				if (best_set_time < best_overall_time){
					best_overall_time = best_set_time;
					best_overall_set_index = j;
				}
				best_set_time = Integer.MAX_VALUE; // Reset variable for the next Subset iteration
			}

			j++; // increment to the next Subset
		}
		
		//If end of the list has been reached, return the optimal Subset index, if it does not exceed the WORK_HOURS time limit
		if (j == num_sets && best_overall_time <= WORK_HOURS){
			return best_overall_set_index;
		}
		
		//End of Subset list reached without finding valid, optimal Subset/permutation
		return -1;
	}
	
	//Check and abort if program has exceeded MAX_TIME Program Run Time Limit
	public static void checkTimeout(long programStartTime, long caseStartTime){
		double currentTime = System.nanoTime();
		double currentProgramRuntime = currentTime - programStartTime;
		if(currentProgramRuntime > MAX_TIME * Math.pow(10, 9)) {
			System.out.println(" Time limit exceeded");
			System.out.printf("\n execution time %.3f ms\n", ((currentTime - caseStartTime) / Math.pow(10, 6)));
			System.exit(1);
		}
	}
	
	//Check if one List contains at least one of the values found in the second List.
	public static boolean listContainsAnyOf(List<Integer> list, List<Integer> multiple_values){
		for (int value : multiple_values){
			if (list.contains(value)){
				return true;
			}
		}
		return false;
	}
	
	//Get the distance between two points
	public static double getDistance(int x1, int y1, int x2, int y2){
		return Math.sqrt(Math.pow(x2-x1, 2) + Math.pow(y2-y1, 2)); 
	}
	
	//Calculates the time needed for Keanu to complete the given path permutation, and the corresponding lab details
	public static double getPathTimeInHours(List<Map<String, Integer>> labs_list, List<Integer> permutation){
		Map<String, Integer> lab_info = labs_list.get(0);
		int homex = lab_info.get("x-coordinate");
		int homey = lab_info.get("y-coordinate");
		int x1 = homex;
		int y1 = homey;
		int x2;
		int y2;
		double total_distance_in_metres = 0.0;
		int permutation_size = permutation.size();
		
		//Iterate through the permutation, checking the distance between all adjacent points and adding it to the permutation's total_distance_in_metres
		for (int i = 0; i < permutation_size; i++){
			lab_info = labs_list.get(permutation.get(i));
			x2 = lab_info.get("x-coordinate");
			y2 = lab_info.get("y-coordinate");
			total_distance_in_metres += getDistance(x1, y1, x2, y2);
			x1 = x2;
			y1 = y2;
		}
		total_distance_in_metres += getDistance(x1, y1, homex, homey);
		
		//Convert the distance (metres) to time (hours) needed for Keanu to complete the trip
		return (total_distance_in_metres / METRES_IN_A_KILOMETRE) / MONKEY_SPEED_KMH;
	}
}
